#include <bits/stdc++.h>

using namespace std;

// 如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。
// 请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。
// 测试链接：https://leetcode.cn/problems/count-stepping-numbers-in-range/

class Solution 
{
public:
    static const int MOD = 1e9 + 7;

    int countSteppingNumbers(string low, string high) 
    {
        return (cnt(high) - cnt(low) + MOD + check(low)) % MOD;
    }

    int cnt(string& s)
    {
        int m = s.size();
        int dp[m][10];
        memset(dp, -1, sizeof dp);
        function<int(int, int, bool, bool)> f = [&](int i, int prev, bool is_limit, bool is_num) -> int
        {
            // is_num 为 true 表示得到了一个合法数字
            if(i == m) return is_num;
            if(!is_limit && is_num && dp[i][prev] != -1) return dp[i][prev];
            int ans = 0;
            // 可以跳过当前数位
            if(!is_num) ans = f(i + 1, prev, false, false);
            // 如果前面填的数字都和 s 的一样，那么这一位至多填数字 s[i]（否则就超过 s 啦）
            int up = is_limit ? s[i] - '0' : 9;
            for(int d = 1 - is_num; d <= up; ++d)  // 枚举要填入的数字 d
            {
                if(!is_num || abs(d - prev) == 1)
                {
                    // 第一位数字随便填，其余必须相差 1
                    ans = (ans + f(i + 1, d, is_limit && d == up, true)) % MOD;
                }
            }
            if(!is_limit && is_num) dp[i][prev] = ans;
            return ans;
        };

        return f(0, 0, true, false);
    }

    bool check(string& s)
    {
        for(int i = 1; i < s.size(); ++i)
        {
            if(abs(s[i] - s[i - 1]) != 1) return false;
        }
        return true;
    }
};